package com.code;

/**
 * 算法导论 切钢条
 * Created by lucky on 2018/9/29.
 */
public class CuttingSteel {

    public static int[] v = {0,1,5,8,9,10,17,17,20,24,30};

    public static int[] r = new int[101];

    public static void main(String[] args) {
        for(int j = 1 ;j <= 10 ; j++){
            r[j] = -1;
        }
        for (int i=1 ; i<=10;i++){
//            System.out.println(CutRod(v,i));
//            System.out.println(cut_rod(i));
            System.out.println(BottomUpCutRod(v,i));
        }
    }

    public static int CutRod(int[] p, int n)
    {
        if (n == 0)
        {
            return 0;
        }

        int q = -1;
        for (int i = 1; i <= n; ++i)
        {
            int tmp = p[i] + CutRod(p, n - i);
            if (q < tmp)
            {
                q = tmp;
            }
        }

        return q;
    }

    /**   
     * @author zflu
     * @Description 带备忘录切法
     * @date 2018/9/29 15:26
     * @param [n]  
     * @return int  
     */ 
    public static int cut_rod(int n)//左端最优解为p，右端钢板剩余长度n，对右端继续切割
    {
        if (n == 0) return 0;
        if(r[n] != -1){
            return r[n];
        }
        int q = -99999999;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, v[i] + cut_rod(n - i));//cut_rod(n)返回长度为n的钢棒，所能获得的最大价值

        }
        r[n] = q;
        return q;
    }

    /**   
     * @author zflu
     * @Description 自低向上  
     * @date 2018/9/29 11:26
     * @param [p, n]  
     * @return int  
     */ 
    public static int BottomUpCutRod(int[] p ,int n){
        int[] r = new int[n+1];
        r[0] = 0;
        for (int i=1;i<=n;i++){
            int q = -1;
            for (int j = 1 ; j<=i;j++){
                int temp = p[j] + p[i-j];
                if(q < temp){
                    q = temp;
                }
            }
            r[i] = q;
        }
        return r[n];
    }


}
